package leetcode;
import java.util.Queue;
import java.util.LinkedList;
/**
 * 101.对称二叉树
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 */
public class Num_101 {
    /** 方法一：递归 **/
    public boolean isSymmetric(TreeNode root) {
        if(root.left == null && root.right == null){
            return true;
        }
        if(root.left == null ^ root.right == null){
            return false;
        }
        if(root.left.val != root.right.val){
            return false;
        }
        return isMirror(root.left,root.right);
    }
    //判断两棵树是否镜像对称
    public boolean isMirror(TreeNode left,TreeNode right) {
        if(left == null && right == null){
            return true;
        }
        if(left == null ^ right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        return isMirror(left.left,right.right) && isMirror(left.right,right.left);
    }

    /** 方法二：层序遍历，借助队列 **/
    public boolean isSymmetric2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        // 添加根节点的左右子树
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()){
            //每次弹出一组轴对称的两个节点进行比较
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if(t1 == null && t2 == null){
                //当前组的两个节点都为null，再比较下一组
                continue;
            }else if(t1 == null ^ t2 == null){
                return false;
            }else if(t1.val != t2.val){
                return false;
            }else{
                //两个对称的节点值相同，再比较它们的子树
                //左节点的左子树和右节点的右子树
                queue.offer(t1.left);
                queue.offer(t2.right);
                //左节点的右子树和右节点的左子树
                queue.offer(t1.right);
                queue.offer(t2.left);
            }
        }
        return true;
    }
}
